import numpy as np
class P:
    def __init__(self,matrix,g):
        self.matrix=matrix
        self.father=None
        self.g=g
    def setg(self,g):
            self.g=g
    def setfather(self,B):
        self.father=B

OPEN=[]#用于未被拓展的储存矩阵
CLOSED=[]#用于已被拓展的储存矩阵
Cvalue=[]#储存未被拓展的矩阵估价函数值

def h1(Pa,Pb):#获取两个矩阵每一数码与目标数码之间的距离总和
 num=0
 for x in range(n):
   for y in range(n):

     for i in range(n):
        for j in range(n):
           if (Pa[i,j] == Pb[x,y] & Pb[x,y] != 0):
             num=num+abs(x-i)+abs(y-j)
             break
             break
 return num

def changex(i,P2,x,y): #交换后要获得错位数目
    P2[x,y], P2[x + i, y] = P2[x + i,y], P2[x,y]
    return h1(Pn.matrix,P2)
def changey(i,P2,x,y):
    P2[x,y], P2[x,y+i] = P2[x, y+i], P2[x,y]
    return h1(Pn.matrix,P2)

def printf(P0):  # 用于最后输出
    print("正序路径如下：")
    print("初始状态为：")
    for row in P1.matrix:
        print(row)
    print("*****************")
    G = []
    while P0.father is not None:
        G.append(P0)
        P0 = P0.father
    for P0 in reversed(G):
        print("第%d次移动后为："%P0.g)
        for row in P0.matrix:
            print(row)
        print("*****************")

#移动矩阵（顺序为上下左右）
def display(P0):
 global n  #这样在函数内就可以改变全局变量，如果没有global函数会自动重新创建一个变量
 if (h1(Pn.matrix, P0.matrix)==0):
     print("搜索成功")
     printf(P0)
     exit()
 for x in range(n):
    for y in range(n):
      if(P0.matrix[x,y]==0):
        P2LIST=[]#储存暂时当前一层矩阵
        if(0 < x & x < n-1):#左右边界内
            if(0 < y & y < n-1):#上下边界内
                #可以向上下左右移动
                for i in (-1,1):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(changex(i,P2,x,y)+P0.g+1)
                    #changex返回值是.g：错位部分
                    P2LIST.append(P2)
                for i in (-1,1):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(changey(i, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
            else:#中间的最上面或最下面，可以进行左、右、上/下移
                for i in (-1, 1):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(changex(i, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
                if (y==n-1):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(changey(-1, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
                elif (y==0):#上方则下移
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(changey(1, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
        else:
            if (0 < y & y < n-1):
                #m=3
                if (x == n-1):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(changex(-1, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
                elif (x == 0):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(changex(1, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
                for i in (-1, 1):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(changey(i, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
            else:
                if (x == n-1):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(changex(-1, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
                elif (x == 0):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(changex(1, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
                if (y==n-1):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(changey(-1, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)
                elif (y==0):
                    P2 = np.copy(P0.matrix)
                    Cvalue.append(changey(1, P2, x, y)+P0.g+1)
                    P2LIST.append(P2)

        # 检查新创建的矩阵是否与已有的状态重复：
        f=0    # 用于跟踪正在处理的元素在P2LIST中的位置。
        for PX in OPEN:
            if (h1(PX.matrix,P0.matrix)==0):   # 这里如何判断两个矩阵相等：判断错位数目
                del OPEN[f]  #OPEN删除P0
            f=f+1
        CLOSED.append(P0)      #CLOSED加入P0

        f = 0
        for PX in P2LIST:
            flag = 0
            ZPLIST=OPEN+CLOSED
            for PY in ZPLIST:  # 防止出现重复的情况
                if (h1(PX, PY.matrix) == 0):
                    flag = 1
            if (flag == 1):
                del P2LIST[f]
            f = f + 1
        for PX in P2LIST:
            PN=P(PX,P0.g+1)
            PN.setfather(P0)#构建关系
            OPEN.append(PN)

        m = min(Cvalue)
        for PX in OPEN:
            if h1(PX.matrix,Pn.matrix)+PX.g==m:
                Cvalue.remove(m)
                display(PX)

if __name__ == '__main__':

    n=int(input("请输入3或4（分别对应八数码和十五数码）:"))
    if (n == 3):
        L1 = np.asmatrix(np.array([1, 0, 3, 7, 2, 4, 6, 8, 5]).reshape(3, 3))
        # L1=np.asmatrix(np.array([4,1,3,2,0,5,7,8,6]).reshape(3,3))

    elif (n == 4):
        L1 = np.asmatrix(np.array([1,2,0,5,12,14,4,6,11,13,3,7,10,9,15,8]).reshape(4, 4))
    P1 = P(L1, 0)
    print("初始矩阵为：\n", P1.matrix)
    if (n == 3):
        L = np.asmatrix(np.array([1, 2, 3, 8, 0, 4, 7, 6, 5]).reshape(3, 3))
    elif (n == 4):
        L = np.asmatrix(np.array([1,2,3,4,12,13,14,5,11,0,15,6,10,9,8,7]).reshape(4, 4))
    Pn = P(L, 0)
    print("目标矩阵为：\n", Pn.matrix)
    print();
    display(P1)